/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 13, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a set of non-overlapping intervals, insert a new interval
 *              into the intervals (merge if necessary).
 * 
 *              You may assume that the intervals were initially sorted
 *              according to their start times.
 * 
 *              Example 1: Given intervals [1,3],[6,9], insert and merge [2,5]
 *              in as [1,5],[6,9].
 * 
 *              Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and
 *              merge [4,9] in as [1,2],[3,10],[12,16].
 * 
 *              This is because the new interval [4,9] overlaps with
 *              [3,5],[6,7],[8,10].
 */
public class InsertInterval {

	private class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}

		@Override
		public String toString() {
			return start + " " + end;
		}
	}

	Comparator<Interval> comp = new Comparator<Interval>() {

		@Override
		public int compare(Interval o1, Interval o2) {
			if (o1.start < o2.start)
				return -1;
			if (o1.start > o2.start)
				return 1;
			if (o1.end < o2.end)
				return -1;
			if (o1.end > o2.end)
				return 1;
			return 0;
		}
	};

	public ArrayList<Interval> insert(ArrayList<Interval> intervals,
			Interval newInterval) {
		intervals.add(newInterval);
		if (intervals.size() < 2)
			return intervals;
		ArrayList<Interval> res = new ArrayList<Interval>();
		Collections.sort(intervals, comp);
		int s = intervals.get(0).start;
		int e = intervals.get(0).end;
		for (int i = 1; i < intervals.size(); i++) {
			if (s <= intervals.get(i).start && e >= intervals.get(i).end) {
				continue;
			} else if (intervals.get(i).start <= e)
				e = intervals.get(i).end;
			else {
				res.add(new Interval(s, e));
				s = intervals.get(i).start;
				e = intervals.get(i).end;
			}
		}
		res.add(new Interval(s, e));

		return res;
	}

	@Test
	public void test() {
		ArrayList<Interval> intervals = new ArrayList<Interval>();
		intervals.add(new Interval(1, 2));
		intervals.add(new Interval(3, 5));
		intervals.add(new Interval(6, 7));
		intervals.add(new Interval(8, 10));
		intervals.add(new Interval(12, 16));

		for (Interval in : insert(intervals, new Interval(4, 9))) {
			System.out.println(in);
		}
	}

}
